package day_2022_7_to_8.day48;

import java.util.*;

/**
 * @author haomin
 * @date 2022/08/07 11:12
 **/
public class Day23_3_Num6139_ReachableNodes {
    class Solution {
        public int reachableNodes(int n, int[][] edges, int[] restricted) {
            int res = 0;
            List<Integer>[] list = new List[n];
            for (int i = 0; i < n; i++) {
                list[i] = new ArrayList<>();
            }
            int[] isRest = new int[n];
            Arrays.fill(isRest, -1);
            for (int re : restricted) isRest[re] = 1;
            for (int[] edge : edges) {
                int a = edge[0], b = edge[1];
                list[a].add(b);
                list[b].add(a);
            }
            Queue<int[]> que = new LinkedList<>();
            que.add(new int[]{0, -1});
            res++;
            while (!que.isEmpty()) {
                int[] p = que.poll();
                int cur = p[0], pre = p[1];
                for (int node : list[cur]) {
                    if (isRest[node] != 1 && node != pre) {
                        res++;
                        que.add(new int[]{node, cur});
                    }
                }
            }
            return res;
        }
    }


//    public int reachableNodes(int n, int[][] edges, int[] restricted) {
//        Set<Integer> set = new HashSet<>();
//        Queue<Integer> queue = new LinkedList<>();
//        for(int i : restricted) {
//            queue.offer(i);
//            set.add(i);
//        }
//        while(!queue.isEmpty()){
//            int cur = queue.poll();
//            for(int[] edge : edges){
//                if(edge[0] == cur && edge[1] != 0){
//                    if(set.add(edge[1])) queue.offer(edge[1]);
//                }else if(edge[0] != 0 && edge[1] == cur){
//                    if(set.add(edge[0])) queue.offer(edge[0]);
//                }
//            }
//        }
//        return n - set.size();
//    }
}